package _20_十大排序算法;

import java.util.Arrays;

// 数组的数据规模不断缩小，直到剩下最后一个元素，然后在将元素合并排序，这就是归并排序
// 归并排序的时间复杂度为n(logn)
public class _04_归并排序 {

    public static void main(String[] args) {

        _04_归并排序 v = new _04_归并排序();
        int[] ins = new int[]{2, 3, 1, 5, 4, 2};

        v.mergeSort(ins);

        System.out.println(Arrays.toString(ins));

    }

    // 将数据规模不断拆分至最小，然后将最小的数组有序合并
    public void mergeSort(int[] nums) {
        split(nums, 0, nums.length);
    }

    // 不断拆分成子元素
    public void split(int[] nums, int begin, int end) {
        if (end - begin <= 1) return;

        int mid = begin + end >> 1;

        split(nums, begin, mid);
        split(nums, mid, end);

        merge(nums, begin, mid, end);
    }

    // 合并两个数组
    public void merge(int[] nums, int begin, int mid, int end) {
        int nLen = mid - begin;
        int[] newAry = new int[nLen];
        System.arraycopy(nums, begin, newAry, 0, nLen);
        int left = 0;
        int right = mid;
        int storeIndex = begin;
        while (left < nLen) {
            if (right < end && nums[right] < newAry[left]) {
                nums[storeIndex++] = nums[right++];
            } else {
                nums[storeIndex++] = newAry[left++];
            }
        }
    }

}
